package com.cty.sixthDay;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.Stack;

/*
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
 * */
public class Q_7 {
    public static void main(String[] args) {
        int[] Height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trap = trap4(Height);
        System.out.println(trap);
    }

    //暴力算法 时间复杂度O(n^2) 空间复杂度O(1)
    public static int trap(int[] Height) {
        if (Height == null || Height.length == 0) return 0;
        int left_max, right_max, l = Height.length, ans = 0;
        for (int i = 1; i < l; i++) {
            left_max = 0;
            right_max = 0;
            //在左边寻找 做左边的最大值
            for (int j = 0; j < i; j++) {
                left_max = Math.max(left_max, Height[j]);
            }
            //在右边寻找有右边的最大值
            for (int k = i + 1; k < l; k++) {
                right_max = Math.max(right_max, Height[k]);
            }
            // 判断最小值是否比本身的柱子高
            if (Math.min(right_max, left_max) > Height[i]) {
                ans += Math.min(right_max, left_max) - Height[i];
            }
        }
        return ans;
    }

    //动态规划 用两个数组分别计算出左边最大的柱子高度 右边柱子最大的高度 分别记录下来 最后统一计算即可 时间复杂度O(n) 空间复杂度O(n)
    public static int trap2(int[] Height) {
        int[] left_max_height = new int[Height.length], right_max_height = new int[Height.length];
        int l = Height.length,left_max = 0,right_max = 0,ans = 0;
        //先计算左边的柱子高度
        for (int i = 0; i < l; i++) {
            if (Height[i] > left_max) {
                left_max = Height[i];
                left_max_height[i] = left_max;
            } else {
                left_max_height[i] = left_max;
            }
        }
        for (int i = l - 1; i >= 0; i--) {
            if (Height[i] > right_max) {
                right_max = Height[i];
                right_max_height[i] = right_max;
            } else {
                right_max_height[i] = right_max;
            }
        }
        for (int i = 0;i< l;i++) {
            if (Math.min(left_max_height[i],right_max_height[i]) > Height[i]) {
                ans += Math.min(left_max_height[i],right_max_height[i]) - Height[i];
            }
        }
        return ans;
    }

    //单调递减栈 雨水堆积的条件 必须形成低洼 利用这个条件我们可以用单调递减栈来解决 时间复杂度O(n) 空间复杂度O(n)
    public static int trap3(int[] Height) {
        if (Height == null || Height.length == 0) return 0;
        int ans = 0;
        // 创建一个栈 使其形成单调递减栈
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while (i < Height.length) {
            // 判断当前的高度是否大于上一个柱子的高度
            while (!stack.isEmpty() && Height[stack.peek()] < Height[i]) {
                // 取出上一个柱子的高度
                int top = stack.pop();
                // 取出柱子的高度之后 发现栈为空 说明是越来越高的柱子 无法形成低洼 停止循环
                if (stack.isEmpty()) break;
                // 计算比top这个柱子的高度高的柱子(栈里的柱子)的距离
                int distance = i - stack.peek() - 1;
                // 先计算出两边的柱子那个低 在计算他们所形成低洼储水的面积
                ans += (Math.min(Height[stack.peek()],Height[i]) - Height[top]) * distance;
            }
            // 把当前柱子的索引存进去 在往右移动
            stack.push(i++);
        }
        return ans;
    }

    //双指针法 用双指针 在两边遍历 当前左右指针所指的那根柱子那个低计算那个所能储水的储水量 让这根低的柱子(左/右)边的柱子的最大值 - 该柱子的高度
    //时间复杂度O(n) 空间复杂度O(1)
    public static int trap4(int[] Height) {
        if (Height == null | Height.length == 0) return 0;
        int left = 0,right = Height.length - 1,right_max = 0,left_max = 0,ans = 0;
        while (left < right) {
            // 判断左右两边的谁的高度低 谁的高度低谁做为储水面积的高-本柱子本身的高度
            if (Height[left] > Height[right]) {
                // 右边的柱子的高度最大值比当前右指针所指的柱子高度低 说明没有形成低洼 无法储水
                if (Height[right] > right_max) {
                    right_max = Height[right];
                } else {
                    // 如果当前柱子的高度比右边柱子高度的最大值小 则形成了低洼 计算当前柱子储水的面积(只限于当前柱子的上的)
                    ans += right_max - Height[right];
                }
                right--;
            } else {
                // 与右半侧的情况相同
                if (Height[left] > left_max) {
                    left_max = Height[left];
                } else {
                    ans += left_max - Height[left];
                }
                left++;
            }
        }
        return ans;
    }
}
